package main

import "fmt"

//#link: https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
func main() {
	n := 5
	fmt.Println(fib(n))
}

const (
	Mod = 1e9 + 7
)

//0 1 1 2 3 5
func fib(n int) int {
	if n == 0 {
		return 0
	} else if n == 1 {
		return 1
	} else {
		first, second := 0, 1
		for i := 2; i <= n; i++ {
			first, second = second, (first+second)%Mod
		}
		return second
	}
}
